package com.Questions.DP;


/**
 * 最长重复数组
 */
public class leetcode718 {
    public int findLength(int[] nums1, int[] nums2) {
        int n1=nums1.length;
        int n2=nums2.length;
        int maxLen=0;
        int[][] dp=new int[n1][n2];
        for(int i=0;i<n1;++i){
            for(int j=0;j<n2;++j){
                if(nums1[i]!=nums2[j]){
                    dp[i][j]=0;
                }else{
                    if(j==0||i==0){
                        dp[i][j]=1;
                    }else{
                        dp[i][j]=dp[i-1][j-1]+1;
                    }
                }
                if(dp[i][j]>maxLen){
                    maxLen=dp[i][j];
                }
            }
        }
        return maxLen;
    }
    public int findLength_beta(int[] A, int[] B) {
        int n = A.length, m = B.length;
        int[][] dp = new int[n + 1][m + 1];
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
}
